#include <iostream>
#include <vector>
#include <list>

using namespace std;

// 递归函数来生成所有可能的划分
void generate_partitions(const std::vector<int>& array, int index, std::vector<int>& subset1, std::vector<int>& subset2, std::vector<std::pair<std::vector<int>, std::vector<int>>>& all_partitions) {
    if (index == array.size()) {
        if(subset1.empty()||subset2.empty()){
            return;
        }
        all_partitions.push_back({subset1, subset2});
        return;
    }

    // 将当前元素放入第一个子数组
    subset1.push_back(array[index]);
    generate_partitions(array, index + 1, subset1, subset2, all_partitions);
    subset1.pop_back(); // 回溯

    // 将当前元素放入第二个子数组
    subset2.push_back(array[index]);
    generate_partitions(array, index + 1, subset1, subset2, all_partitions);
    subset2.pop_back(); // 回溯
}

// 打印所有划分
void print_partitions(const std::vector<std::pair<std::vector<int>, std::vector<int>>>& all_partitions) {
    for (const auto& partition : all_partitions) {
        std::cout << "{ ";
        for (int value : partition.first) {
            std::cout << value << " ";
        }
        std::cout << "} | { ";
        for (int value : partition.second) {
            std::cout << value << " ";
        }
        std::cout << "}" << endl;
    }
}